package com.zklh.leetcode.constructor.uf;

/**
 * 被围绕的区域uf解法
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/6/5 16:41
 */
public class SurroundingArea {


    UF uf;

    public void solve(char[][] board) {

        /* 首先把四个边练到dummy, 这里有个小技巧, 并查集的实现是一维数组, 使用 x*n+y的方式表示 x,y的位置, 这是个通用的技巧 n是列数 */
        int m = board.length;
        int n = board[0].length;
        uf = new UFImpl(m * n+1);
        // 连接四个边中'O'节点 和 dummy
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                uf.union(i*n+0, m*n);
            }
            if (board[i][n-1] == 'O'){
                uf.union(i*n+n-1,m*n);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                uf.union(i,m*n);
            }
            if (board[m-1][i] == 'O') {
                uf.union((m-1)*n+i, m*n);
            }
        }

        // 然后对边内元素 分别和上下左右相连, 这里用1,0, 0,1 -1,0, 0,-1标识四个方向
        // 定义四个方向数组
        int[][] directions = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O') {
                    for (int d = 0; d < directions.length; d++) {
                        int x = i + directions[d][0];
                        int y = j + directions[d][1];
                        if (board[x][y] == 'O') {
                            uf.union(i*n+j,x*n+y);
                        }
                    }
                }
            }
        }

        // 找到不和dummy相连的元素 就是被围绕的区域了, 将值替换为'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!uf.connected(i * n + j, m * n)) {
                    board[i][j] = 'X';
                }
            }
        }

    }


    public static void main(String[] args) {
        SurroundingArea surroundingArea = new SurroundingArea();
        char[][] board = new char[][]{
                {'X','X','X','X','O'},
                {'X','X','X','O','X'},
                {'O','O','X','O','X'},
                {'X','O','X','X','X'}
        };
        surroundingArea.solve(board);
    }

}
